#
# @lc app=leetcode.cn id=221 lang=python3
#
# [221] 最大正方形
#

# @lc code=start
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0 for i in range(n)] for j in range(m)]
        res = 0
        for i in range(m):
            dp[i][0] = int(matrix[i][0])
            res = max(res, dp[i][0])
        for j in range(n):
            dp[0][j] = int(matrix[0][j])
            res = max(res, dp[0][j])
        # res = 0
        for i in range(1, m, 1):
            for j in range(1, n, 1):
                if matrix[i][j] == "1":
                    dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
                    res = max(res, dp[i][j])
        return res*res
        
# @lc code=end

